
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}


public class project {
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while (true){
            if(fast==null||fast.next==null){
                return null;
            }
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
        }
        fast=head;
        while (fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }

















    public ListNode reverseList(ListNode head) {
        ListNode prev=null;
        ListNode cur=head;
        while (cur!=null){
            ListNode curNext=cur.next;
            cur.next=prev;
            prev=cur;
            cur=curNext;
        }
        return prev;
    }


















    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead==null||pHead.next==null){
            return null;
        }
        ListNode head=new ListNode(-1);
        head.next=pHead;
        ListNode cur=pHead;
        ListNode prev=cur;
        while (cur!=null&&cur.next!=null){
            int val=cur.val;
            if(val==cur.next.val){
                while (cur!=null&&val==cur.val){
                    cur=cur.next;
                }
                prev.next=cur;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        return head.next;
    }

















    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null&&list2==null){
            return null;
        }
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        ListNode head=new ListNode(-1);
        ListNode cur=head;
        while (list1!=null&&list2!=null){
            int val1=list1.val;
            int val2=list2.val;
            if(val1<val2){
                cur.next=list1;
                list1=list1.next;
            }else{
                cur.next=list2;
                list2=list2.next;
            }
            cur=cur.next;
        }
        if(list1==null){
            cur.next=list2;
        }
        if(list2==null){
            cur.next=list1;
        }
        return head.next;
    }
}
